1. Field of the Invention
The present invention relates generally to an apparatus and method for transmitting/receiving data in a communication system, and in particular, to an apparatus and method for transmitting/receiving data in a multi-antenna communication system using structured Low Density Parity Check (LDPC) codes.
2. Description of the Related Art
Currently, due to the rapid development of communication technologies, communication systems are evolving into high-speed, high-capacity communication systems capable of processing and transmitting a variety of information such as images and radio data, transcending the conventional voice-oriented service. The evolution of high-speed, high-capacity communication systems extends not only to wire networks but also to wireless networks. As a result, there is a need for the development of a technology capable of transmitting high-capacity data, of which the capacity of the wireless network approaches the capacity of the wire network.
To meet the needs of the high-speed, high-capacity communication system, the communication system uses an appropriate channel coding scheme for data transmission/reception to increase the system transmission efficiency, contributing to the improvement of the system performance.
However, the mobile communication system, due to its characteristics, may inevitably suffer from errors caused by noise, interference and fading according to channel conditions during data transmission. Therefore, the mobile communication system suffers a loss of information data due to these errors. In order to reduce information data loss, the mobile communication system uses various error control schemes according to channel characteristics, thereby contributing to the improvement of the system reliability. Of the error control schemes, an error correction code-based error control scheme is most popularly used.
In the next generation mobile communication system, an increase in the number of users who desire to receive more data at higher speed requires an increase in the data rate. In order to meet the user's demands, active research is being conducted on a multi-antenna communication system using multiple transmission/reception antennas, i.e., a Multiple Input Multiple Output (MIMO) communication system.
With reference to the schematic diagram of FIG. 1, a description will now be made of a structure of a transmitter in a general MIMO communication system.
Referring to FIG. 1, the transmitter includes an encoder 110, a spatial mapper 120, and a signal mapping unit 130 connected to a plurality of antennas including a first transmission antenna TxANT#1 to an Mth transmission antenna TxANT#M. The signal mapping unit 130 includes M signal mappers including a first signal mapper 130-1 to an Mth signal mapper 130-M.
The encoder 110 encodes input information data into coded symbols according to a preset coding rate, and outputs the generated coded symbols to the spatial mapper 120.
The spatial mapper 120 spatially-maps serial coded symbols output from the encoder 110 into M parallel signals, where M is the number of antennas. The spatial mapper 120 outputs the parallel signals to their corresponding signal mappers 130-1 to 130-M, respectively. For example, the spatial mapper 120 sequentially parallel-converts the coded symbols output from the encoder 110 into M signals according to their output order, and outputs the M signals to the first signal mapper 130-1 to the Mth signal mapper 130-M, respectively.
The signal mapping unit 130 signal-maps the parallel signals output from the spatial mapper 120 according to a signal mapping scheme preset in each of the signal mappers 130-1 to 130-M, and outputs the signal-mapped signals to their corresponding transmission antennas. That is, each of the first signal mapper 130-1 to the Mth signal mapper 130-M signal-maps the signal output from the spatial mapper 120 according to a constellation preset therein, and outputs the resultant signal to its corresponding transmission antenna.
For example, each of the first signal mapper 130-1 to the Mth signal mapper 130-M signal-maps its input signal using Binary Phase Shift Keying (BPSK) if the number n of bits of the input signal is 1 (n=1), and signal-maps its input signal using 8-ary Quadrature Amplitude Modulation (8 QAM) if the number n of bits of the input signal is 3 (n=3).
Assuming that the number of bits of information data input to the transmitter of FIG. 1 is denoted by k, a coding rate R of the transmitter is
      R    =          M      ×              k        n              ,where M denotes the number of transmission antennas.
With reference to the schematic diagram of FIG. 2, a description will now be made of a structure of a receiver in a general MIMO communication system.
Referring to FIG. 2, the receiver includes a detector 210 connected to a plurality of antennas including a first reception antenna RxAnt#1 to a Pth reception antenna RxAnt#P, a spatial demapper 220, a decoder 230, and a spatial mapper 240.
The number of transmission antennas of the transmitter can be either equal to or different from the number of the reception antennas of the receiver. The receiver receives signals via P reception antennas including the first reception antenna RxAnt#1 to the Pth reception antenna RxAnt#P. The signals received via the first reception antenna RxAnt#1 to the Pth reception antenna RxAnt#P are input to the detector 210.
The detector 210 detects the signals received via the first reception antenna RxAnt#1 to the Pth reception antenna RxAnt#P, and outputs the detected signals to the spatial demapper 220.
The spatial demapper 220 spatially-demaps the signal detected by the detector 210 according to a spatial demapping scheme corresponding to the spatial mapping scheme of the spatial mapper used in the transmitter, and outputs the resultant signal to the decoder 230.
The decoder 230 decodes the signal output from the spatial demapper 220 according to a decoding scheme corresponding to the coding scheme used in the transmitter. The signal output from the decoder 230 can be normally restored to the original data transmitted by the transmitter, when it has not suffered an error in the wireless channel environment. However, the output signal can be subject to iterative decoding for reliable decoding, when it has suffered an error in the wireless channel environment.
To perform the iterative decoding, the decoder 230 outputs the signal decoded with the decoding scheme corresponding to the coding scheme used in the transmitter, to the spatial mapper 240.
The spatial mapper 240 spatially-maps the signal output from the decoder 230 with a spatial mapping scheme corresponding to the spatial mapping scheme used in the transmitter, and outputs the resultant signal back to the detector 210 to thereby perform iterative decoding.
The iterative decoding contributes to an increase in restoration reliability of the information data. After decoding the received signal into a reliable signal through the iterative decoding, the decoder 230 outputs the decoded reliable signal as a final information data signal.
Typical error correction codes include turbo codes and LDPC codes. It is well known that the turbo code is superior in performance gain to a convolutional code conventionally used for error correction, during high-speed data transmission. The turbo code is advantageous in that it can efficiently correct an error caused by noises generated in a transmission channel, thereby increasing reliability of the data transmission. The LDPC code can be decoded using an iterative decoding algorithm based on a sum-product algorithm in a factor graph. Because a decoder for the LDPC code uses the sum-product algorithm-based iterative decoding algorithm, it is lower in complexity than a decoder for the turbo code. In addition, the decoder for the LDPC code is easy to implement with a parallel processing decoder, compared with the decoder for the turbo code.
Shannon's channel coding theorem shows that reliable communication is possible only at a data rate not exceeding a channel capacity. However, Shannon's channel coding theorem has proposed no detailed channel coding/decoding method for supporting a data rate up to the channel capacity limit. Although a random code having a very large block size shows performance approximating the channel capacity limit of Shannon's channel coding theorem, it is actually impossible to implement a Maximum A Posteriori (MAP) or Maximum Likelihood (ML) decoding method because of its heavy calculation load.
The turbo code was proposed by Berrou, Glavieux and Thitimajshima in 1993, and has superior performance approximating the channel capacity limit of Shannon's channel coding theorem. The proposal of the turbo code triggered a research on iterative decoding and graphical expression of codes, and LDPC codes proposed by Gallager in 1962 have been newly spotlighted in the research. Cycles exist in a factor graph of the turbo code and the LDPC code, and it is well known that iterative decoding in the factor graph of the LDPC code where cycles exist is suboptimal. Also, it has been experimentally proven that the LDPC code has excellent performance through iterative decoding. The LDPC code known to have the highest performance shows performance having a difference of only about 0.04 [dB] at the channel capacity limit of Shannon's channel coding theorem at a bit error rate (BER) of 10−5, using a block size of 107. In addition, although an LDPC code defined in Galois field (GF) with q>2, i.e., GF(q), increases in complexity in its decoding process, it is much superior in performance to a binary code. However, there has been provided no satisfactory theoretical description of successful decoding by an iterative decoding algorithm for the LDPC code defined in GF(q).
The LDPC code, proposed by Gallager, is defined by a parity check matrix in which major elements have a value of 0 and minor elements other than the elements having the value of 0 have a non-zero value, for example, i.e., a value of 1. For convenience, it will be assumed herein that the non-zero value is a value of 1.
For example, an (N, j, k) LDPC code is a linear block code having a codeword length N, and is defined by a sparse parity check matrix in which each column has j elements having a value of 1, each row has k elements having a value of 1, and all of the elements other than the elements having the value of 1 have a value of 0.
An LDPC code in which a weight of each column in the parity check matrix is fixed to ‘j’ and a weight of each row in the parity check matrix is fixed to ‘k’ as stated above, is called a “regular LDPC code.” Herein, the “weight” refers to the number of elements having a non-zero value among the elements constituting the generating matrix and parity check matrix. Unlike the regular LDPC code, an LDPC code in which the weight of each column in the parity check matrix and the weight of each row in the parity check matrix are not fixed is called an “irregular LDPC code.” It is generally known that the irregular LDPC code is superior in performance to the regular LDPC code. However, in the case of the irregular LDPC code, because the weight of each column and the weight of each row in the parity check matrix are not fixed, the weight of each column in the parity check matrix and the weight of each row in the parity check matrix must be properly adjusted in order to guarantee the excellent performance.
With reference to the diagram of FIG. 3, a description will now be made of a parity check matrix of an (8, 2, 4) LDPC code as an example of the (N, j, k) LDPC code. Referring to FIG. 3, a parity check matrix H of the (8, 2, 4) LDPC code is comprised of 8 columns and 4 rows, wherein a weight of each column is fixed to 2 and a weight of each row is fixed to 4. Because the weight of each column and the weight of each row in the parity check matrix are regular, the (8, 2, 4) LDPC code illustrated in FIG. 3 is a regular LDPC code.
The parity check matrix of the (8, 2, 4) LDPC code has been described so far with reference to FIG. 3. Next, a factor graph of the (8, 2, 4) LDPC code described in connection with FIG. 3 will be described hereinbelow with reference to the diagram of FIG. 4.
Referring to FIG. 4, a factor graph of the (8, 2, 4) LDPC code is comprised of 8 variable nodes of x1 400, x2 402, x3 404, x4 406, x5 408, x6 410, x7 412 and x8 414, and 4 check nodes 416, 418, 420 and 422. When an element having a value of 1, i.e., a non-zero value, exists at the point where an ith row and a jth column of the parity check matrix of the (8, 2, 4) LDPC code cross each other, a branch is created between a variable node xi and a jth check node. The variable nodes of FIG. 4 can be considered as being mapped to the (8, 2, 4) LDPC codewords c=[c1, c2, c3, c4, c5, c6, c7, c8] on a one-to-one basis. That is, it can be considered that the codeword c1 is mapped to the variable node xi, the codeword c2 is mapped to the variable node x2, the codeword c3 is mapped to the variable node x3, the codeword c4 is mapped to the variable node x4, the codeword c5 is mapped to the variable node x5, the codeword c6 is mapped to the variable node x6, the codeword c7 is mapped to the variable node x7, and the codeword c8 is mapped to the variable node x8, respectively. Therefore, the (8, 2, 4) LDPC code can be decoded by delivering messages through the variable nodes and the check nodes in the factor graph, and the codewords can be estimated based on the messages of the variable nodes.
Because the parity check matrix of the LDPC code has a very small weight as described above, it is possible to perform decoding through iterative decoding even in a block code having a relatively long size, that exhibits performance approximating a channel capacity limit of Shannon's channel coding theorem, such as a turbo code, while continuously increasing a block size of the block code. MacKay and Neal have proven that an iterative decoding process of an LDPC code using a flow transfer scheme approximates an iterative decoding process of a turbo code in performance.
In order to generate a high-performance LDPC code, the following conditions should be satisfied.
(1) Cycles in a Factor Graph of an LDPC Code Should be Considered.
The term “cycle” refers to a loop formed by the edges connecting the variable nodes to the check nodes in a factor graph of an LDPC code, and a length of the cycle is defined as the number of edges constituting the loop. A long cycle means that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is large. In contrast, a short cycle means that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is small.
As cycles in the factor graph of the LDPC code become longer, the performance efficiency of the LDPC code increases, for the following reasons. That is, when long cycles are generated in the factor graph of the LDPC code, it is possible to prevent performance degradation such as an error floor occurring when too many cycles with a short length exist in the factor graph of the LDPC code.
(2) Efficient Coding of an LDPC Code Should be Considered.
It is difficult for the LDPC code to undergo real-time coding compared with a convolutional code or a turbo code because of its high coding complexity. In order to reduce the coding complexity of the LDPC code, a Repeat Accumulate (RA) code has been proposed. However, the RA code also has a limitation in reducing the coding complexity of the LDPC code. Therefore, efficient coding of the LDPC code should be taken into consideration.
(3) Degree Distribution in a Factor Graph of an LDPC Code Should be Considered.
Generally, an irregular LDPC code is superior in performance to a regular LDPC code, because a factor graph of the irregular LDPC code has various degrees. The term “degree” refers to the number of edges connected to the variable nodes and the check nodes in the factor graph of the LDPC code. Further, the phrase “degree distribution” in a factor graph of an LDPC code refers to a ratio of the number of nodes having a particular degree to the total number of nodes. It has been proven by Richardson that an LDPC code having a particular degree distribution is superior in performance.
With reference to the schematic diagram of FIG. 5, a description will now be made of a parity check matrix of a structured LDPC code.
Before a description of FIG. 5 is given, it should be noted that the structured LDPC code is a new LDPC code for which not only efficient coding but also efficient storage and performance improvement of a parity check matrix were considered, and the structured LDPC code is an LDPC code extended by generalizing a structure of a regular LDPC code.
Referring to FIG. 5, a parity check matrix of the structured LDPC code is divided into a plurality of partial blocks, and a permutation matrix is mapped to each of the partial blocks. Herein, a matrix obtained by substituting 1 for each of the partial blocks instead of the permutation matrix is referred to as a base matrix. That is, the parity check matrix of the structured LDPC code can be considered as a matrix obtained by mapping the permutation matrix to a point where 1 is located in the base matrix. Generally, however, the matrix constituting the parity check matrix of the structured LDPC code is not restricted to the permutation matrix. In FIG. 5, ‘P’ represents a permutation matrix having an Ns×Ns size, and a superscript apq of the permutation matrix P is either 0≦apq≦Ns−1 or apq=∞. 
In addition, ‘p’ indicates that a corresponding permutation matrix is located in the pth row of the partial blocks of the parity check matrix, and ‘q’ indicates that a corresponding permutation matrix is located in the qth column of the partial blocks of the parity check matrix. That is, papq represents a permutation matrix located in a partial block where the pth row and the qth column of the parity check matrix comprised of a plurality of partial blocks cross each other. That is, the ‘p’ and the ‘q’ represent the number of rows and the number of columns of partial blocks in the parity check matrix, respectively.
FIG. 6 is a diagram illustrating the permutation matrix P of FIG. 5. As illustrated in FIG. 6, the permutation matrix P is a square matrix having an Ns×Ns size, and each of Ns columns constituting the permutation matrix P has a weight of 1 and each of Ns rows constituting the permutation matrix P also has a weight of 1. Herein, although a size of the permutation matrix P is expressed as Ns×Ns, it will be expressed as Ns for convenience because the permutation matrix P is a square matrix.
In FIG. 5, a permutation matrix P with a superscript apq=0, i.e. a permutation matrix P0, represents an identity matrix INs×Ns, and a permutation matrix P with a superscript apq=∞, i.e. a permutation matrix P∞, represents a zero matrix. Herein, INs×Ns represents an identity matrix with a size Ns×Ns.
In the entire parity check matrix of the structured LDPC code illustrated in FIG. 5, because the total number of rows is Ns×p and the total number of columns is Ns×q (for p≦q), when the entire parity check matrix of the structured LDPC code has a full rank, a coding rate can be expressed as Equation (1) regardless of a size of the partial blocks.
                    R        =                                                                              N                  s                                ×                q                            -                                                N                  s                                ×                p                                                                    N                s                            ×              q                                =                                                    q                -                p                            q                        =                          1              -                              p                q                                                                        (        1        )            
If apq≠∞ for all p and q, the permutation matrixes corresponding to the partial blocks are not zero matrixes, and the partial blocks constitute a regular LDPC code in which the weight value of each column and the weight value of each row in each of the permutation matrixes corresponding to the partial blocks are p and q, respectively. Herein, each of permutation matrixes corresponding to the partial blocks will be referred to as a “partial matrix.”
Because (p−1) dependent rows exist in the entire parity check matrix, a coding rate is greater than the coding rate calculated by Equation (1). In the case of the structured LDPC code, if a weight position of a first row of each of the partial matrixes constituting the entire parity check matrix is determined, the weight positions of the remaining (Ns−1) rows can be determined. Therefore, the required size of a memory is reduced to 1/Ns as compared with the case where the weights are irregularly selected to store information of the entire parity check matrix.
As described above, the term “cycle” refers to a loop formed by the edges connecting the variable nodes to the check nodes in a factor graph of an LDPC code, and a length of the cycle is defined as the number of edges constituting the loop. A long cycle means that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is large. As cycles in the factor graph of the LDPC code become longer, the performance efficiency of the LDPC code increases.
In contrast, as cycles in the factor graph of the LDPC code become shorter, an error correction capability of the LDPC code increases because performance degradation such as an error floor occurs. That is, when there are many cycles with a short length in a factor graph of the LDPC code, information on a particular node belonging to the cycle with a short length, starting therefrom, returns after a small number of iterations. As the number of iterations increases, the information returns to the corresponding node more frequently, so that the information cannot be correctly updated, thereby causing a deterioration in an error correction capability of the LDPC code.
FIG. 7 is a diagram schematically illustrating a cycle structure of a structured LDPC code of which a parity check matrix is comprised of 4 partial matrixes.
A parity check matrix of the structured LDPC code illustrated in FIG. 7 is comprised of 4 partial blocks, a diagonal line represents a position where the elements having a value of 1 are located, and the parts other than the diagonal-lined parts represent positions where the elements having a value of 0 are located. In addition, ‘P’ represents the same permutation matrix as the permutation matrix described in conjunction with FIG. 6.
In order to analyze a cycle structure of the structured LDPC code illustrated in FIG. 7, an element having a value of 1 located in an ith row of a partial matrix Pa is defined as a reference element, and an element having a value of 1 located in the ith row will be referred to as a “0-point.” Herein, “partial matrix” will refer to a matrix corresponding to the partial block. The 0-point is located in an (i+a)th column of the partial matrix pa.
An element having a value of 1 in a partial matrix Pb, located in the same row as the 0-point, will be referred to as a “1-point.” For the same reason as the 0-point, the 1-point is located in an (i+b)th column of the partial matrix Pb.
Next, an element having a value of 1 in a partial matrix Pc, located in the same column as the 1-point, will be referred to as a “2-point.” Because the partial matrix Pc is a matrix acquired by right shifting respective columns of an identity matrix I with respect to a modulo Ns by c, the 2-point is located in an (i+b−c)th row of the partial matrix Pc.
In addition, an element having a value of 1 in a partial matrix Pd, located in the same row as the 2-point, will be referred to as a “3-point.” The 3-point is located in an (i+b−c+d)th column of the partial matrix Pd.
Finally, an element having a value of 1 in the partial matrix pa, located in the same column as the 3-point, will be referred to as a “4-point.” The 4-point is located in an (i+b−c+d−a)th row of the partial matrix Pa.
In the cycle structure of the LDPC code illustrated in FIG. 7, if a cycle with a length 4 exists, the 0-point and the 4-point are located in the same position. That is, a relation between the 0-point and the 4-point is defined by Equation (2):i≅i+b−c+d−a(mod Ns) ori+a≅i+b−c+d(mod Ns)  (2)
Equation (2) can be rewritten as Equation (3):a+c≅b+d(mod Ns)  (3)
As a result, when the relationship of Equation (3) is satisfied, a cycle with a length 4 is generated. Generally, when a 0-point and a 4p-point are at first identical to each other, a relation of i≅i+p(b−c+d−e)(mod Ns) is given, and the following relation shown in Equation (4) is satisfied.p(a−b+c−d)≅0(mod Ns)  (4)
In other words, for given a, b, c and d, if a positive integer having a minimum value among the positive integers satisfying Equation (4) is defined as ‘p’, a cycle with a length of 4p becomes a cycle having a minimum length in the cycle structure of the structured LDPC code illustrated in FIG. 7.
In conclusion, as described above, for (a−b+c−d)≠0, if gcd (greatest common divisor)(Ns, a−b+c−d)=1 is satisfied, then p=Ns. Therefore, a cycle with a length 4Ns becomes a cycle with a minimum length.
As described above, it is known that the LDPC code, together with the turbo code, has a high performance gain during high-speed data transmission and effectively corrects an error caused by noises generated in a transmission channel, contributing to an increase in reliability of data transmission.
Meanwhile, the foregoing structured parity check matrix is designed to satisfy the design conditions of the parity check matrix to guarantee excellent performance. Therefore, the LDPC code, when it is designed with the structured parity check matrix, can not only satisfy the foregoing conditions but also facilitate the coding/decoding process, increasing attention to the structured LDPC code. The use of the structured LDPC code in the multi-antenna communication system can secure not only a high data rate but also a high reliability. Research is being presently conducted to build a communication system using the structured LDPC code.
The current communication system using the structured LDPC code transmits/receives the structured LDPC code bit by bit. For example, in the multi-antenna communication system, for bit-by-bit transmission of the structured LDPC code, it is necessary to design a bit-based check matrix of the structured LDPC code in order to design a structured LDPC code that guarantees high performance.
When the structured LDPC code is used, a size of the partial blocks is varied to support a variable length. In this case, if the structured LDPC code is mapped to a plurality of antennas, different mapping methods should be considered to guarantee excellent performance for different lengths. That is, it is necessary to construct the variable-length structured LDPC code with a different matrix for each length.
To address these problems, there is a need for a transceiver capable of efficiently transmitting/receiving the structured LDPC code, compared with transmitting/receiving the structured LDPC code bit by bit. In addition, there is a need to apply the structured LDPC code to a multi-antenna system, considered as one of the next generation communication systems.